package DynamicProgramming;
/**
 * P264 丑数 II
 * */
public class P264 {
}

class P264Test01{
    public int nthUglyNumber(int n) {
        int[] ans=new int[n];
        ans[0]=1;
        int p2=0,p3=0,p5=0;
        for(int i=0;i<n;i++){
            int num=Math.min(ans[p2]*2,Math.min(ans[p3]*3,ans[p5]*5));
            ans[i]=num;
            if(num==ans[p2]*2) p2++;
            if(num==ans[p3]*3) p3++;
            if(num==ans[p5]*5) p5++;
        }
        return ans[n-1];

    }
}